Binary tree

Create binary tree

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

Pre-order

let preorderDfs = (node) => {
  if (!node) {
    return;
  }

  console.log(node.val);
  preorderDfs(node.left);
  preorderDfs(node.right);
  return;
};

In-order

let inorderDfs = (node) => {
  if (!node) {
    return;
  }

  inorderDfs(node.left);
  console.log(node.val);
  inorderDfs(node.right);
  return;
};

Post-order

let postorderDfs = (node) => {
  if (!node) {
    return;
  }

  postorderDfs(node.left);
  postorderDfs(node.right);
  console.log(node.val);
  return;
};

DFS - recursion

let dfs = (root) => {
  if (!root) {
    return;
  }

  let ans = 0;

  // do logic
  dfs(root.left);
  dfs(root.right);
  return ans;
};

DFS - iteration

let dfs = (root) => {
  let stack = [root];
  let ans = 0;

  while (stack.length) {
    let node = stack.pop();
    // do logic
    if (node.left) {
      stack.push(node.left);
    }
    if (node.right) {
      stack.push(node.right);
    }
  }

  return ans;
};

BFS

let fn = (root) => {
  let queue = [root];
  let ans = 0;

  while (queue.length) {
    let currentLength = queue.length;
    // do logic for current level

    let nextQueue = [];

    for (let i = 0; i < currentLength; i++) {
      let node = queue[i];
      // do logic
      if (node.left) {
        nextQueue.push(node.left);
      }
      if (node.right) {
        nextQueue.push(node.right);
      }
    }

    queue = nextQueue;
  }

  return ans;
};

Examples

DFS - Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

var maxDepth = function (root) {
  if (!root) {
    return 0;
  }

  let left = maxDepth(root.left);
  let right = maxDepth(root.right);

  return Math.max(left, right) + 1;
};

DFS - Path Sum

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

var hasPathSum = function (root, targetSum) {
  const checkPath = (node, sum) => {
    if (!node) {
      return 0;
    }

    if (!node.left && !node.right) {
      return node.val + sum === targetSum;
    }

    sum += node.val;
    let left = checkPath(node.left, sum);
    let right = checkPath(node.right, sum);
    return left || right;
  };

  return checkPath(root, 0);
};

DFS - Diameter of Binary Tree

Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them

var diameterOfBinaryTree = function (root) {
  let maxDiameter = 0;
  function dfs(node) {
    if (!node) {
      return 0;
    }

    let left = dfs(node.left);
    let right = dfs(node.right);

    maxDiameter = Math.max(maxDiameter, left + right);
    return Math.max(left, right) + 1;
  }

  dfs(root);
  return maxDiameter;
};

Binary search tree

Range Sum of BST

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

var rangeSumBST = function (root, low, high) {
  if (!root) {
    return 0;
  }

  let ans = 0;
  if (low <= root.val && root.val <= high) {
    ans += root.val;
  }
  if (low < root.val) {
    ans += rangeSumBST(root.left, low, high);
  }
  if (root.val < high) {
    ans += rangeSumBST(root.right, low, high);
  }

  return ans;
};